Solid-state memory devices encompass rewritable non-volatile memory devices which use electronic circuitry for storing data. Currently, solid-state memory devices start replacing conventional storage devices such as hard disk drives and optical disk drives in some arenas, such as in mass storage applications for laptops or desktops. Solid state memory devices are also investigated for replacing conventional storage devices in other areas such as in enterprise storage systems. This is because solid state memory devices offer exceptional bandwidth as well as excellent random I/O (input/output) performance along with an appreciated robustness due to lack of moveable parts.
However, writing data to flash memory devices requires paying attention to specifics in the flash technology: NAND Flash memory is organized in units of pages and blocks. Multiple pages form a block. While read and write operations can be applied to pages as a smallest unit of such operation, erase operations can only be applied to entire blocks. And while in other storage technologies outdated data can simply be overwritten by new data, flash technology requires an erase operation before new data can be written to an erased block.
For the reason that in flash technology erase operations take much longer than read or write operations, a writing technique is applied called “write out of place” in which new or updated data is written to some free page offered by a free page allocator instead of writing it to the same page where the outdated data resides. The page containing the outdated data is marked as invalid page. At some point in time, a process called “garbage collection” frees blocks for new writes by moving the content of all valid pages of a block to free pages at different blocks. As a result, the subject block finally comprises invalid pages only and can be erased. While this procedure requires some additional write and read operations in excess, it is apparent that by such approach immediate as well as frequent erase operations are avoided which would contribute to a much higher overall processing than an overhead of some additional write and read operations do.
However, it is also apparent that the write out of place and garbage collection processes require support from a management structure for translating the physical addresses at which the data is stored in the flash memory into logical addresses used by upper layer systems interacting with the present storage system, and vice versa. A means for supporting such translation may be an LBA to PBA mapping table (Logical Block Address to Physical Block Address) or an LPN to PPN mapping table (Logical Page Number to Physical Page Number) subject to a block or page resolution of the mapping. A management structure including such address mapping means and corresponding routines may advantageously be implemented in a controller of the solid state memory device and is called flash translation layer (FTL) for flash applications specifically. The flash translation layer hides any address translation against the host such that the flash translation layer can be understood as a management structure that emulates the flash memory device as an LBA accessible storage device to the host.
A main memory of the storage controller may be a preferred location for depositing the address mapping information for various reasons. This certainly is feasible for small flash memory sizes. However, with an increase in flash memory capacity, the address mapping information also increases to a level where the entire mapping information will cause the main memory size go beyond economic efficiency.
Several techniques are proposed to alleviate this problem. Specifically, in “DFTL: A Flash Translation Layer Employing Demand-based Selective Caching of Page-level Address Mappings” by A. Gupta et al., in ASPLOS'09, Mar. 7-11, 2009, Washington, D.C., USA, accessed and retrieved on the Internet at http://csl.cse.psu.edu/publications/dftl-asplos09.pdf on Jul. 8, 2010, a Demand-based Flash Translation Layer DFTL is proposed in which the entire logical-to-physical address translation set is maintained on some logically fixed portion of flash and is referred to as the Global Mapping Table. However, only a small number of these mappings can be present in SRAM. These active mappings present in SRAM form the Cached Mapping Table (CMT). Since out-of-place updates are performed on flash, translation pages get physically scattered over the entire flash memory. DFTL keeps track of all these translation pages on flash by using a Global Translation Directory (GTD). When servicing a request the following process of address translation is used: If the required mapping information for the given read/write request exists in SRAM (in CMT), it is serviced directly by reading/writing the data page on flash using this mapping information. If the information is not present in SRAM then it needs to be fetched into the CMT from flash prior to reading/writing the data page on flash. However, depending on the state of CMT and the replacement algorithm being used, it may entail evicting entries from SRAM.